package com.lx.algorithm.code.xly3.class08;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-25 16:45:39
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-25     张李鑫                     1.0         1.0 Version
 */
public class Code02 {
    /**
     * 现有n1+n2种面值的硬币，其中前n1种为普通币，
     * 可以取任意枚，后n2种为纪念币， 每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值?
     */
    public static int moneyWays(int[] arr, int[] arr1, int m) {
        if (arr.length == 0 && arr1.length == 0) {
            return 0;
        }
        return process(arr, arr1, 0, 0, m);
    }


    private static int process(int[] n1, int[] n2, int i, int i2, int m) {
        if (i == n1.length && i2 == n2.length) {
            return m == 0 ? 1 : 0;
        }

        if (i == n1.length) {
            return process(n2, i2, m);
        }
        int ans = 0;
        int count = m / n1[i];

        for (int i1 = 0; i1 <= count; i1++) {
            ans += process(n1, n2, i + 1, i2, m - (i1 * n1[i]));
        }
        return ans;
    }


    public static int process(int[] n2, int i, int m) {
        if (i == n2.length) {
            return m == 0 ? 1 : 0;
        }
        return process(n2, i + 1, m) + process(n2, i + 1, m - n2[i]);
    }


    public static int dpII(int[] n1, int[] n2, int m) {
        int l = n1.length;
        int l1 = n2.length;
        int[][] dp = new int[l + 1][m + 1];
        dp[l][0] = 1;
        for (int i = l - 1; i >= 0; i--) {
            dp[i][0] = 1;
            for (int j = 1; j <= m; j++) {
                dp[i][j] = j - n1[i] >= 0 ? dp[i][j - n1[i]] + dp[i + 1][j] : dp[i + 1][j];
            }
        }

        int[][] dpII = new int[l1 + 1][m + 1];
        dpII[n2.length][0] = 1;
        for (int i = l - 1; i >= 0; i--) {
            dpII[i][0] = 1;
            for (int j = 1; j <= m; j++) {
                dpII[i][j] = dpII[i + 1][j] + j - n2[i] >= 0 ? dpII[i + 1][m - n2[i]] : 0;
            }
        }
        for (int i = m; i >= 0; i--) {
            for (int j = 0; j < l1; j++) {
                dp[n1.length][i] += dpII[j][m];
            }
        }

        return 0;
    }


    public static int dp(int[] arr, int[] arr1, int m) {
        if (arr.length == 0 && arr1.length == 0) {
            return 0;
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] n1 = {5, 1, 3, 10};
        int[] n2 = {2, 2, 1, 1, 3, 3, 3, 10};
        System.out.println(dpII(n1, n2, 10));
    }
}


